package org.example.chap01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {

    public static void main(String[] args) {

        int[] nums = {-1,0,1,2,-1,-4};

//        List<int[]> result = solution1(nums,0);
//        for (int i = 0; i < result.size(); i++) {
//            int[] intArray = result.get(i);
//            for (int num:intArray){
//                System.out.print(num+" ");
//            }
//            System.out.println("==================");
//        }

        //算法2
        List<List<Integer>> list =  solution2(nums);
        for (int i = 0; i < list.size(); i++) {
            List<Integer> listInt = list.get(i);
            System.out.println(listInt.toString());
        }
    }

    /**
     * 时间复杂度是O(n^3)
     * @param nums
     * @param target
     * @return
     */
    public static List solution1(int[] nums,int target){

        List<int[]> list = new ArrayList<>();

        for (int i = 0; i < nums.length-2; i++) {
            for (int j = i+1; j < nums.length-1; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if(nums[i]+nums[j]+nums[k] == target){
                        int[] result = new int[3];
                        result[0]=nums[i];
                        result[1]=nums[j];
                        result[2]=nums[k];
                        boolean isEqual = judgeArray(list,result);
                        if(isEqual == false){
                            list.add(result);
                            System.out.println("找到了");
                        }

                    }
                }
            }
        }
        return  list;
    }

    public static boolean judgeArray(List<int[]> list,int[] nums){

        Arrays.sort(nums);

        for (int i = 0; i < list.size(); i++) {
            int[] result = list.get(i);
            Arrays.sort(result);
            boolean isEqual=Arrays.equals(result,nums);
            if(isEqual==false){
                continue;
            }
            return isEqual;
        }
        return false;
    }

    /**
     * 首先对数组进行排序，排序后固定一个数 nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]后面的两端，
     * 数字分别为 nums[L]nums[L] 和 nums[R]nums[R]，计算三个数的和 sumsum 判断是否满足为 00，满足则添加进结果集
     * 如果 nums[i]nums[i]大于 00，则三数之和必然无法等于 00，结束循环
     * 如果 nums[i]nums[i] == nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
     * 当 sumsum == 00 时，nums[L]nums[L] == nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++L++
     * 当 sumsum == 00 时，nums[R]nums[R] == nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R--R−−
     * 时间复杂度：O(n^2)
     * {-1,0,1,2,-1,-4};
     * @param nums
     * @return
     */
    public static List<List<Integer>> solution2(int[] nums){
        List<List<Integer>> ans = new ArrayList<>();
        //如果当前数据长度小于3，则不满足条件
        if(nums==null || nums.length<3){
            return ans;
        }
        //按照从小到大的顺序排序
        Arrays.sort(nums);
        int len = nums.length;
        // {-4,-1,-1,0,1,2};
        for (int i = 0; i < len; i++) {
            //安全验证，如果当前最小值大于0，则不满足条件，跳出
            if(nums[i]>0){
                break;
            }
            //去重
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int L=i+1;
            int R=len-1;
            while (L<R){
                int sum = nums[i]+nums[L]+nums[R];
                if(sum == 0){
                    //加入到列表中
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    //去重
                    while (L < R && nums[L] == nums[L+1]){
                        L++;
                    }
                    while (L <R && nums[R] == nums[R-1]){
                        R--;
                    }
                    //匹配成功后，两边指针都要向中间移动
                    L++;
                    R--;

                }else if(sum<0){
                    L++;
                }else if(sum>0){
                    R--;
                }
            }
        }

        return ans;
    }
}
